#region Copyright (c) 2003 - 2008, Andreas Mueller
/////////////////////////////////////////////////////////////////////////////////////////
// 
// Copyright (c) 2003 - 2008, Andreas Mueller.
// All rights reserved. This program and the accompanying materials
// are made available under the terms of the Eclipse Public License v1.0
// which accompanies this distribution, and is available at
// http://www.eclipse.org/legal/epl-v10.html
//
// Contributors:
//    Andreas Mueller - initial API and implementation
//
// 
// This software is derived from software bearing the following
// restrictions:
// 
// Copyright (c) 1994
// Hewlett-Packard Company
// 
// Permission to use, copy, modify, distribute and sell this software
// and its documentation for any purpose is hereby granted without fee,
// provided that the above copyright notice appear in all copies and
// that both that copyright notice and this permission notice appear
// in supporting documentation.  Hewlett-Packard Company makes no
// representations about the suitability of this software for any
// purpose.  It is provided "as is" without express or implied warranty.
// 
// 
// Copyright (c) 1996,1997
// Silicon Graphics Computer Systems, Inc.
// 
// Permission to use, copy, modify, distribute and sell this software
// and its documentation for any purpose is hereby granted without fee,
// provided that the above copyright notice appear in all copies and
// that both that copyright notice and this permission notice appear
// in supporting documentation.  Silicon Graphics makes no
// representations about the suitability of this software for any
// purpose.  It is provided "as is" without express or implied warranty.
// 
// 
// (C) Copyright Nicolai M. Josuttis 1999.
// Permission to copy, use, modify, sell and distribute this software
// is granted provided this copyright notice appears in all copies.
// This software is provided "as is" without express or implied
// warranty, and with no claim as to its suitability for any purpose.
// 
/////////////////////////////////////////////////////////////////////////////////////////
#endregion
using System;
using System.Collections;
using System.Collections.Generic;
using NStl.Iterators;
using NStl.Iterators.Support;
using NStl.Linq;
using NStl.NUnit.Support;
using NUnit.Framework;
using NUnit.Framework.SyntaxHelpers;

namespace NStl.NUnit.AlgorithmFixtures.Merge
{
    public abstract class MergeBaseFixture : AlgorithmBaseFixture
    {
        protected abstract OutputIt
            DoMerge<T, OutputIt>(IInputIterator<T> first1, IInputIterator<T> last1,
                                 IInputIterator<T> first2, IInputIterator<T> last2,
                                 OutputIt result) 
            where OutputIt : IOutputIterator<T>
            where T: IComparable<T>;
        [Test]
        public override void SuccessfullPass()
        {

            ICollection expected = new IdentifiableInteger[]
                                       {
                                           0, 1, 2, 3, 4, 4, 5, 6, 6, 7, 8, 9
                                       };

            List<int> v1 = new List<int> { 0, 2, 4, 4, 8 };
            List<int> v2 = new List<int> { 1, 3, 5, 6, 6, 7, 9 };

            LinkedList<int> target = new LinkedList<int>();
            target.Resize(v1.Count + v2.Count);

            LinkedListIterator<int> endOfTarget =
                DoMerge(v1.Begin(), v1.End(), v2.Begin(), v2.End(),
                        target.Begin());

            Assert.That(target, Is.EqualTo(expected));
            Assert.That(endOfTarget, Is.EqualTo(target.End()));
        }
        [Test]
        public void SuccessfullPassWithStableOrder()
        {
            IdentifiableInteger i0 = new IdentifiableInteger(0);
            IdentifiableInteger i1 = new IdentifiableInteger(1);
            IdentifiableInteger i2 = new IdentifiableInteger(2);
            IdentifiableInteger i3 = new IdentifiableInteger(3);
            IdentifiableInteger i4 = new IdentifiableInteger(4);
            IdentifiableInteger i4_2 = new IdentifiableInteger(4);
            IdentifiableInteger i5 = new IdentifiableInteger(5);
            IdentifiableInteger i6 = new IdentifiableInteger(6);
            IdentifiableInteger i6_2 = new IdentifiableInteger(6);
            IdentifiableInteger i7 = new IdentifiableInteger(7);
            IdentifiableInteger i8 = new IdentifiableInteger(8);
            IdentifiableInteger i9 = new IdentifiableInteger(9);


            List<IdentifiableInteger> v1 = new List<IdentifiableInteger> { i0, i2, i4, i4_2, i8 };
            List<IdentifiableInteger> v2 = new List<IdentifiableInteger> { i1, i3, i5, i6, i6_2, i7, i9 };

            LinkedList<IdentifiableInteger> target = new LinkedList<IdentifiableInteger>();
            target.Resize(v1.Count + v2.Count);

            LinkedListIterator<IdentifiableInteger> endOfTarget =
                DoMerge(v1.Begin(), v1.End(), v2.Begin(), v2.End(),
                        target.Begin());


            // Verify stable sort
            List<int> ids = new List<int>();

            Func<IdentifiableInteger, int> extractId = i => i.ID;
            Algorithm.Transform(target.Begin(), target.End(), ids.AddLastInserter(), Functional.PtrFun(extractId));

            Assert.That(Algorithm.IsSorted(ids.Begin(), ids.End()), Is.True);
            Assert.That(endOfTarget, Is.EqualTo(target.End()));
        }
        public override void NonSuccessfullPass()
        {
            throw new NotImplementedException("The method or operation is not implemented.");
        }
        [Test]
        public override void StartIteratorIsEqualToEndIterator()
        {
            List<int> v1 = new List<int> { 0, 2, 4, 8 };
            List<int> v2 = new List<int> { 1, 3, 5, 6, 7, 9 };

            ICollection expected = v2.ToArray();

            LinkedList<int> target = new LinkedList<int>();
            target.Resize(v2.Count);

            LinkedListIterator<int> endOfTarget =
                DoMerge(v1.Begin(), v1.Begin(), v2.Begin(), v2.End(),
                        target.Begin());

            Assert.That(target, Is.EqualTo(expected));
            Assert.That(endOfTarget, Is.EqualTo(target.End()));
        }
        [Test]
        public void SecondStartIteratorIsEqualToSecondEndIterator()
        {
            List<int> v1 = new List<int> { 0, 2, 4, 8 };
            List<int> v2 = new List<int> { 1, 3, 5, 6, 7, 9 };

            ICollection expected = v1.ToArray();

            LinkedList<int> target = new LinkedList<int>();
            target.Resize(v1.Count);

            LinkedListIterator<int> endOfTarget =
                DoMerge(v1.Begin(), v1.End(), v2.Begin(), v2.Begin(),
                        target.Begin());

            Assert.That(target, Is.EqualTo(expected));
            Assert.That(endOfTarget, Is.EqualTo(target.End()));
        }
        [Test]
        public void EmptyRanges()
        {
            List<int> v1 = new List<int>();
            List<int> v2 = new List<int>();

            LinkedList<int> target = new LinkedList<int>();

            LinkedListIterator<int> endOfTarget =
                DoMerge(v1.Begin(), v1.End(), v2.Begin(), v2.End(),
                        target.Begin());

            Assert.That(target, Is.Empty);
            Assert.That(endOfTarget, Is.EqualTo(target.Begin()));
        }
    }
}